package com.str.graphs;

import com.str.queue.Queue;

public class TopSort {
  private static void printout(int v) {
    System.out.print(v + " ");
  }

  public static void topsortD(Graph g) { // Topological sort: recursive
    boolean[] visited = new boolean[g.n()];
    for (int i=0; i<g.n(); i++)
      visited[i] = false;       // Initialize Mark array
    for (int i=0; i<g.n(); i++)   // Process all vertices
      if (!visited[i])
        topsortD(g, i, visited);   // Call recursive helper function
  }
  
  private static void topsortD(Graph g, int v, boolean[] visited) { // Process vertex v
    visited[v] = true;
    // No PreVisit operation
    for (int w = g.first(v); w < g.n(); w = g.next(v,w))
      if (!visited[w])
        topsortD(g, w, visited);
    printout(v);	    // PostVisit for Vertex v
  }
  
  public static void topsortB(Graph g, Queue queue) {   // Topological sort: Queue
    int[] count = new int [g.n()];

    for (int v=0; v < g.n(); v++) count[v] = 0; // Initialize
    for (int v=0; v < g.n(); v++)  // Process every edge
      for (int w = g.first(v); w < g.n(); w = g.next(v,w))
        count[w]++;   // Add to v2's prereq count
    for (int v=0; v < g.n(); v++)  // Initialize Queue
      if (count[v] == 0)     // Vertex has no prerequisites
        queue.enqueue(new Integer(v));
    while (!queue.isEmpty()) {   // Process the vertices
      Integer i = (Integer)(queue.dequeue());
      int v = i.intValue();
      printout(v);  	   // PreVisit for Vertex V
      for (int w = g.first(v); w < g.n(); w = g.next(v,w)) {
        count[w]--;    // One less prerequisite
        if (count[w] == 0) // This vertex is now free
	      queue.enqueue(new Integer(w));
      }
    }
    System.out.println();
  }
}
